//【案例开放014】1204上机编程“任务规划”学习交流
//贪心 算法 greedy algorithm
//【案例开放014】1204上机编程“任务规划”学习交流
// 1.   题目
//今天学习1204上机编程工作级第3题/专业级第1题。题目：任务规划
//任务列表 tasks 中有 N 个任务，任务编号 Ni​ 的值范围为 [0,
// N-1]。 由于存在资源竞争，某些任务间存在两两互斥关系，并记录在二维数组
// mutexPairs 中，该二维数组元素为 [Ni​, Nj​]，其中
// Ni​，Nj​ 为互斥的两个任务编号。 现在需要对任务列表
// tasks
//进行切割分组。要求： l
// 存在互斥关系的任务不能分在同一组 l  单个任务也可以单独一组 l
// 一个任务可能和多个任务互斥 请判断 最少 可以将任务列表 tasks 切割
//成几组？（即：切割后的小组是原列表的 连续子数组） 示例 1： 输入：tasks =
//[1,4,2,3,0], mutexPairs = [] 输出：1 解释：无互斥关系，所有任务可分在同一组。
//示例 2：
//输入：tasks = [1,3,2,4,6,5,0], mutexPairs = [[1,3],[4,5]]
//输出：3
//解释：任务1，3 不能被分在同一组；4，5
//不能被分在同一组，所以最终只能将任务列表分成3组。例如，[1],[3,2,4,6],[5,0]
//为其中一种分法；[1],[3,2,4],[6,5,0] 为另一种分法。
//注意：切割后的小组是原列表的连续子数组。
//示例 3：
//输入：tasks = [0,1,2,3,4,5], mutexPairs = [[1,3],[3,5]]
//输出：3
//解释：最少分成 3 组。例如，[0,1,2],[3,4],[5] 为其中一种分法。
//提示：
// 2.   题目分析
//题目理解：
//将一个数组最少切割为几个子数组，使得每个子数组中的任务id不存在互斥关系。
//注意一个任务可能和多个任务互斥，互斥不具有传递性。
//从题目（见加粗的连续子数组）和示例可以得知，是顺序切割任务列表数组（如果不按顺序切割，复杂度比按顺序切割要高很多）。
// tasks 中有 N 个任务，任务编号的值范围为 [0, N-1]说明任务id是不重复的。
//解题思路：
//以示例2为例，tasks = [1,3,2,4,6,5,0], mutexPairs = [[1,3],[4,5]]
//已知任务1和3互斥、4和5互斥。求最少需要将数组切换为几部分？
//我们先理一下解题思路：
//从前往后遍历tasks数组，第一个元素tasks[0]=1，肯定不会有冲突；
//遍历到第二个元素3的时候，因为3和1不能在一个组中，所以需要切割；于是我们自然容易想到需要先把互斥信息记录下来。
//在遍历到没有冲突的任务时，需要把和它互斥的任务ID插入到一个集合中，这样才能快速判断后面的任务是否和前面的冲突。
//解题过程：
// 1)
// 首先记录互斥信息，与1互斥的有{3}、与3互斥的有{1}、与4互斥的有{5}、与5互斥的有{4}。注意：可能是多对多的互斥。
// 2)
// 创建一个与当前子序列互斥的集合mutexSet，然后从头到尾遍历任务列表，有两种情况：
//(a)当前任务id不在互斥集合mutexSet中，就把与当前任务id互斥的数字加入mutexSet；
//(b)当前任务id在互斥集合mutexSet中，ans++，清空mutexSet。
//注：当前子序列指的是从上一个切割点到当前任务之间的所有任务id的列表，子数组指的是拆分后的数组，集合指的是set或者数组、链表等。
//如下图所示：
// mutexSet的作用就是保存当前子序列中各个任务互斥的其它任务id，以上图为例：
// l
// 遍历到3时：找到第一个切割点，mutexSet为空；当前任务3互斥的任务为1，所以mutexSet.insert(1);
// l
// 遍历到4时：当前任务4互斥的任务为5，所以mutexSet.insert(5);此时mutexSet内容为{1,5}
// l  遍历到5时：当前任务5在互斥集合mutexSet中，切割点加1，清空mutexSet。
//此时可以将与5互斥的4添加到集合，即mutexSet内容为{4}；由于任务id不重复，后面不会再出现4了，所以不添加4也可以。
//可以总结为：当前没有互斥的则贪心前进，遇到互斥的则递增ans并清空互斥集合。
//员工3-C++代码：39行、最大圈复杂度10
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define DEBUG
#ifdef DEBUG
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif

class Solution {
 public:
  int DivideGroup(const vector<int>& tasks,
                  const vector<vector<int>>& mutexPairs) {
    if (tasks.size() == 0) {
      return 0;
    }
    if (mutexPairs.size() == 0) {
      return 1;
    }
    int maxV = 200000;
    vector<int> index(tasks.size(), 0);
    for (int i = 0; i < tasks.size(); i++) {
      index[tasks[i]] = i;
    }
    vector<int> M(tasks.size(), maxV);
    for (int i = 0; i < mutexPairs.size(); i++) {
      int left = index[mutexPairs[i][0]];
      int right = index[mutexPairs[i][1]];
      if (left > right) {
        swap(left, right);
      }
      if (right < M[left]) {
        M[left] = right;
      }
    }
    int res = 0;
    int min_value = maxV;
    for (int i = 0; i < tasks.size(); i++) {
      if (i == min_value) {
        min_value = M[i];
        res++;
      } else {
        min_value = min(min_value, M[i]);
      }
    }
    res++;
    return res;
  }
};
//该解法同样与众不同，并不是通过map建立互斥对，而是：
// 1)    首先用数组index当做hash将每个任务id在数组中的索引idx记录下来
// 2)    接下来定义一个数组M，记录每一个索引idx对应的互斥任务的idx
// 3)    最后在遍历任务列表的时候，M[i]就是下一个分割点。
//当前任务索引left在左侧，对应的互斥任务right在右侧。如果有多个互斥任务，只保留离当前索引最近的（M[left]
//= right）。 灵活应用C++标准库中的swap函数实现两个变量的交换。
//在提交的所有C++代码中，这个解法速度是最快的（168ms）。可以优化的地方：
// l  第三行：int DivideGroup(...) { 最右边的花括号应该另起一行。
// l  圈复杂度10稍微有点大
